package org.bear.array;

import java.util.*;

public class Solution {

//    给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
//    [-2,0,0,2,2]
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int i = 0;
        while (i < nums.length){
            int target = -nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if (nums[left]>target && nums[left]>0){
                    break;
                }
                if (nums[left] + nums[right] == target){
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    while (left<nums.length && nums[left]==nums[left-1]){
                        left++;
                    }
                    right--;
                    while (right>0 && nums[right]==nums[right+1]){
                        right--;
                    }
                } else if (nums[left] + nums[right] < target) {
                    left++;
                    while (left<nums.length && nums[left]==nums[left-1]){
                        left++;
                    }
                } else {
                    right--;
                    while (right>0 && nums[right]==nums[right+1]){
                        right--;
                    }
                }
            }
            i++;
            while (i<nums.length && nums[i]==nums[i-1]){
                i++;
            }
        }
        return res;
    }


//    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if (n==0){
            return 0;
        }
        int res = n+1;
        int i = 0;
        int windowValue = 0;
        for(int j=0;j < n && i<=j; j++){
            windowValue += nums[j];
            while (windowValue>=target && i<=j){
                res = Math.min(res, j-i+1);
                windowValue-=nums[i];
                i++;
            }


        }
        if (res==n+1){
            res = 0;
        }
        return res;
    }


    //    给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0;
        int i=0;
        int product = 1;
        for (int j=0;j<nums.length;j++){
            product *= nums[j];
            while (product>=k & i<j){
                product /= nums[i];
                i++;
            }
            if (product<k){
                res += (j-i+1);
            }
        }
        return res;
    }


    // 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> sumMap = new HashMap<>();
        int sum = 0;
        int res = 0;
        for(int i=0;i<nums.length;i++){
            Integer c = sumMap.get(sum);
            if (c==null){
                sumMap.put(sum, 1);
            }else {
                sumMap.put(sum, c+1);
            }
            sum += nums[i];
            res += sumMap.getOrDefault(sum-k, 0);
        }
        return res;
    }


    // 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
    public int findMaxLength(int[] nums) {
        int res = 0;
        Map<Integer, Integer> subMap = new HashMap<>();
        subMap.put(0, -1);
        // num1 - num0
        int diff = 0;
        for(int i=0;i<nums.length;i++){
            diff+=(nums[i]*2-1);
            Integer v = subMap.get(diff);
            if(v==null){
                subMap.put(diff, i);
                v = i;
            }
            res = Math.max(res, i-v);
        }
        return res;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findMaxLength(new int[]{1,0,0}));
    }
}
